package leetcode101.dynamic_planning;

import java.util.*;

/**
 * @author Synhard
 * @version 1.0
 * @Class Code9
 * @Description 139. 单词拆分
 * 给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
 *
 * 说明：
 *
 * 拆分时可以重复使用字典中的单词。
 * 你可以假设字典中没有重复的单词。
 * 示例 1：
 *
 * 输入: s = "leetcode", wordDict = ["leet", "code"]
 * 输出: true
 * 解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
 * 示例 2：
 *
 * 输入: s = "applepenapple", wordDict = ["apple", "pen"]
 * 输出: true
 * 解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
 *      注意你可以重复使用字典中的单词。
 * 示例 3：
 *
 * 输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
 * 输出: false
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-04-14 9:27
 */
public class Code9 {

    public static void main(String[] args) {
        String s = "applepenapple";
        String[] wordDict = new String[]{"apple", "pen"};
        wordBreak(s, Arrays.asList(wordDict));
    }

    public static boolean wordBreak(String s, List<String> wordDict) {

        Map<Integer, List<String>> directory = new HashMap<>();
        for (String temp : wordDict) {
            directory.computeIfAbsent(temp.length(), k -> new ArrayList<>());
            directory.get(temp.length()).add(temp);
        }

        boolean[] dp = new boolean[s.length() + 2];
        dp[0] = true;
        dp[1] = true;

        for (int i = 2; i < dp.length; i++) {
            for (int j = i - 1; j > 0; j--) {
                List<String> temp = directory.get(i - j);
                if (dp[j] && temp!=null && temp.contains(s.substring(j - 1, i - 1))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[dp.length - 1];
    }
}
/*
这道题居然也能用动态规划我也是惊了
dp[0] = true
dp[i] 代表前i - 1个能否符合条件
令 1 <= j <= i - 1
dp[i] = dp[j] && check(s.subString[j - 1, i - 1])
 */
